6、统计子矩阵

题目 统计子矩阵

image-00f7d1e8

思路分析

二维前缀和

没有固定方块大小 所以可能得每个长宽都枚举

得四重循环 一定会超时

但是一时半会确实没想到可优化的点

另外 k有18位 得用long long

代码实现

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=510;

LL a[N][N],s[N][N];

int main()

{

  int n,m,k;

  cin>>n>>m>>k;

  for(int i=1;i<=n;i++){

    for(int j=1;j<=m;j++){

      cin>>a[i][j];

      s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];

    }

  }

  LL cnt=0;

  for(int x1=1;x1<=n;x1++){

    for(int y1=1;y1<=m;y1++){

      for(int x2=x1;x2<=n;x2++){

        for(int y2=y1;y2<=m;y2++){

          int sum=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];

          if(sum<=k)

            cnt++;

        }

      }

    }

  }

  cout<<cnt;

  return 0;

}

同类题型

视频讲解

⬅️ 5、X进制减法 🏠 00-刷题理模型 ➡️ 7、积木画